package m202405.d12;

import java.util.ArrayList;
import java.util.List;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/5/12 13:27
 */
public class Q54 {

    public static void main(String[] args) {
        Q54 q54 = new Q54();
        q54.spiralOrder(new int[][]{
                {1, 2, 3, 4},
                {5, 6, 7, 8},
                {9, 10, 11, 12},
                {13, 14, 15, 16}
        });
    }

    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> rs = new ArrayList<>();
        int n = matrix.length;
        int m = matrix[0].length;
        State state = new State(m, n);
        int i = 0;
        while (i < m * n) {
            rs.add(matrix[state.cy][state.cx]);
            state.walk();
            i++;
        }
        return rs;
    }

    private static class State {
        //0-右，1-下，2-左，3-上
        private int direction = 0;
        private int left = 0;
        private int right;
        private int top = 0;
        private int bottom;

        private int cx = 0;
        private int cy = 0;

        public State(int right, int bottom) {
            this.right = right;
            this.bottom = bottom;
        }

        private void walk() {
            if (direction == 0) {
                if (cx < right - 1) {
                    cx++;
                } else {
                    direction = 1;
                    cy++;
                    top++;
                }
            } else if (direction == 1) {
                if (cy < bottom - 1) {
                    cy++;
                } else {
                    direction = 2;
                    cx--;
                    right--;
                }
            } else if (direction == 2) {
                if (cx > left) {
                    cx--;
                } else {
                    direction = 3;
                    cy--;
                    left++;
                }
            } else {
                if (cy > top) {
                    cy--;
                } else {
                    direction = 0;
                    cx++;
                    bottom--;
                }
            }
        }
    }
}
